package com.zh.note.leetcode.stackqueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 1047. 删除字符串中的所有相邻重复项
 * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 * <p>
 * 在 S 上反复执行重复项删除操作，直到无法继续删除。
 * 输入："abbaca"
 * 输出："ca"
 */
public class LC_1047_removeDuplicates {

    public String removeDuplicates(String s) {
        String str = "";
        char[] chars = s.toCharArray();
        // 栈，存储遍历过的元素
        Deque<Character> stack = new LinkedList<>();
        for (char ch : chars) {
            if (stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else {
                // 当前遍历元素与栈顶元素相同
                stack.pop();
            }

        }
        while (!stack.isEmpty()) {
            str = stack.pop() + str;
        }
        return str;

    }
}
